package com.mdnote.structure.treeapplication;

import javax.activation.CommandObject;
import java.util.*;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/1
 * @description 赫夫曼树
 */
public class HuffmanTree {

    private static class Node implements Comparable<Node> {

        private int val;

        private Node left;

        private Node right;

        public Node(int val) {
            this.val = val;
        }

        // 大的在前面
        @Override
        public int compareTo(Node o) {
            return this.val - o.val;
        }
    }

    /**
     * 创建赫夫曼树
     * @param array 数组
     * @return 根节点
     */
    public static Node build(int[] array) {
        // 对元素进行排序
        List<Node> arrayList = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            arrayList.add(new Node(array[i]));
        }
        Collections.sort(arrayList);

        while (arrayList.size() > 1) {
            // 选取最小的两个元素构建霍夫曼树
            Node leftNode = arrayList.get(0);
            Node rightNode = arrayList.get(1);
            Node rootNode = new Node(leftNode.val + rightNode.val);

            rootNode.left = leftNode;
            rootNode.right = rightNode;

            // 移除那两个元素、把两个元素的和放入集合中
            arrayList.remove(leftNode);
            arrayList.remove(rightNode);
            arrayList.add(rootNode);

            Collections.sort(arrayList);
        }
        return arrayList.get(0);
    }

    public static void main(String[] args) {
        int[] array = {13, 7, 8, 3, 29, 6, 1};
        Node root = build(array);
        preOrder(root);
    }

    private static void preOrder(Node node) {
        System.out.print(node.val + " ");

        if (node.left != null) {
            preOrder(node.left);
        }
        if (node.right != null) {
            preOrder(node.right);
        }
    }

}
